perm filename SECT3[0,BGB] blob
sn#113296 filedate 1974-07-29 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00013 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00003 00002 {⊂C<NF3αGEOMED.λ30P30I425,0JCFA} SECTION 3.
C00007 00003 As in the previous chapter, the programming notation used
C00011 00004
C00014 00005 ⊂3.1 Euler Primitives.⊃
C00020 00006 ⊂3.2 Routines using Euler Primitives.⊃
C00023 00007
C00024 00008 ⊂3.3 Euclidean Routines: Trams - Transforms and Frames.⊃
C00027 00009
C00028 00010 ⊂3.4 Euclidean Routines: Metrics and Space.⊃
C00029 00011 ⊂3.5 Image Synthesis: Perspective Projection.⊃
C00031 00012 ⊂3.6 Image Synthesis: Clipping.⊃
C00032 00013 ⊂3.7 Image Analysis: Interface to CRE.⊃
C00033 ENDMK
C⊗;
{⊂C;<N;F3;αGEOMED.;λ30;P30;I425,0;JCFA} SECTION 3.
{JCFD} A GEOMETRIC MODELING SYSTEM.
{λ10;W250;JAFA}
3.0 Introduction to GEOMED.
3.1 Euler Primitives.
3.2 Routines using Euler Primitives.
3.3 Euclidean Routines: Trams - Transforms and Frames.
3.4 Euclidean Routines: Metrics and Space.
3.5 Image Synthesis: Perspective Projection.
3.6 Image Synthesis: Clipping.
3.7 Image Analysis: Interface to CRE.
{λ30;W0;I950,0;JUFA}
⊂3.0 Introduction to GEOMED.⊃
GEOMED (Geometric Editor) is a system of subroutines for
manipulating winged edge polyhedra. The system has two distinctly
different manifestations: first, it appears as an interactive 3-D
drawing program and second, it appears as a geometric modeling
command language. It is the latter manifestation along with some of
the details of implementation that is the subject of this chapter.
The interactive drawing program is documented in [Baumgart 74]. As a
language, GEOMED is all semantics with no particular syntax of its
own; there are about two hundred subroutines which take from zero to
four arguments, return one or no values and which usually have
considerable side effects on the data structures. The subroutines
can be grouped into five classes: utility routines, Euler routines,
Euclidean routines, image synthesis and image analysis routines. The
utility routines (which will not be further detailed) include
input/output, trigonmetric functions, memory management, a command
scanner and device dependent display routines. The Euler routines
perform topological operations on links, the Euclidean routines
perform geometric computations on data and the image synthesis
routines perform photographic simulations on the model as a whole.
The fifth class, image analysis routines, exists primarily as an
interface between GEOMED and CRE, and consequently lacks the logical
cleanliness and completeness of the other parts of the system.
As in the previous chapter, the programming notation used
will continue to have an ALGOL appearance with specific examples of
actual GEOMED code being given in the language SAIL (Stanford ALGOL)
as is example #1 immediately below. The program in example #1 creates
two cubic prisms and displays them rotating. The header file,
GEOMES.HDR, is kept on a disk area [GEM,HE] and contains the names
of the necessary load modules, the declarations of all the modeling
routines and SAIL macros for accessing GEOMED data structures. After
the header, the first routine to execute is MKUNIV (make universe),
which initializes the data structures. Next two polyhedra are
created using the MKCUBE routine which takes three arguments: width,
breadth and height for specifying a rectangular right parallelepiped.
All such creation routines return an integer which is the absolute
machine address of the GEOMED node of the entity created. The next
routine used is GEODPY which refreshs the display of the model.
Finally, the example calls TRANSL and ROTATE which perform
translation and rotation. TRANSL takes four argument: first the
thing to be moved followed by the three components of a translation
vector; similarly ROTATE takes four arguments: first the thing to be
moved followed by the three components of a rotation vector. (Indeed,
there are several other ways to specify translation and rotation;
these are but the first).
{λ7;W100;JAF3}
BEGIN "EXAMPLE ONE"
REQUIRE "GEOMES.HDR[GEM,HE]" SOURCE_FILE; COMMENT DECLARE GEOMED EMBEDDED IN SAIL;
DEFINE π="3.1415927";
INTEGER B1,B2;
MKUNIV; COMMENT INITIALIZE THE DATA STRUCTURES;
B1 ← MKCUBE(2,4,8); COMMENT CREATE A COUPLE OF CUBIC PRISMS;
B2 ← MKCUBE(1,2,4);
GEODPY; COMMENT NO OPTIONS DISPLAY REFRESH;
TRANSL(B2,-2,2,0); COMMENT DISPLACE ONE OF THEM;
WHILE TRUE DO COMMENT GO FOREVER;
BEGIN
GEODPY; COMMENT DISPLAY REFRESH;
ROTATE(B1,π/10,π/12,π/13); COMMENT ACTION;
ROTATE(B2,-π/14,π/16,-π/17);
END;
END "EXAMPLE ONE";{λ30;W0;JUFA;}
In example #2, the model of a robot arm is read in and the
first three joints are run through a simulated arm motion. The
routine INB3D reads a B3D polyhedron file from the disk. The arm was
draw from measurements using the interactive form of GEOMED. The
FDNAME, find name, routine retrieves a body by its print name;
FDNAME returns zero when a name is not found. The routine INCAM reads
in a camera file. Finally, the routine SHOW2 calls the hidden line
eliminator; when SHOW2's arguments are zero default options are
assumed.
{λ7;W200;JAF3;}
BEGIN "EXAMPLE TWO"
REQUIRE "GEOMES.HDR[GEM,HE]" SOURCE_FILE;
DEFINE αα="COMMENT";
INTEGER B1,B2,J1,J2,J3,J4,J5,J6,C1,CHR,I;
MKUNIV;GEODPY;
B1 ← INB3D("ARM[DAT,BGB]"); αα MODEL OF THE YELLOW ARM;
B2 ← INB3D("TABLE[DAT,BGB]"); αα MODEL OF THE HAND/EYE TABLE;
J1 ← FDNAME("JOINT1"); αα SHOULDER - ABOUT VERTICAL;
J2 ← FDNAME("JOINT2"); αα ARM - ABOUT HORIZONTAL;
J3 ← FDNAME("JOINT3"); αα SLIDE;
J4 ← FDNAME("JOINT4"); αα WRIST TWIST;
J5 ← FDNAME("JOINT5"); αα WRIST FLAP;
J6 ← FDNAME("JOINT6"); αα HAND;
C1 ← INCAM("ARMCAM[DAT,BGB]");
SHOW2(0,0); αα HIDDEN LINE ELIMINATION;
FOR I←0 THRU 70 DO
BEGIN
ROTATE(-J1,0,0,π/18);
ROTATE(-J2,0,0,π/20);
TRANSL(-J3,0,0,0.1);
SHOW2(0,0);
END;
END "EXAMPLE TWO";
{λ30;W0;JUFA;}
⊂3.1 Euler Primitives.⊃
The Euler routines of GEOMED are based on the idea that an
arbitrary polyhedron can be created in steps that always maintain the
Euler relation: F-E+V=2*(B-H). Topologically, a simply connected
Eulerian polyhedral graph can be built up with only four creation
primitives: MKBFV, MKEV, MKFE and GLUEE or taken apart with four
kill primitives: KLBFEV, KLEV, KLFE and UNGLUEE. The prefixes "MK"
and "KL", stand for <make> and <kill>; the initials "B", "F", "E"
and "V" invariably stand for <body, face, edge> and <vertex> and
tend to appear in that order. The notion of <GLUE> is associated with
the process of froming (or removing) a handle which increase (or
decreases) the topological genus of the surface by one unit. The
MKBFV primitive takes no arguments and creates a degenerate point
polyhedron of one vertex, one face and one body which is the minimal
non-zero binding satisfying the Euler equation. The MKEV creates a
new edge and a new vertex attached to the given vertex in the given
face. The MKFE creates a new face and a new edge, the new edge is
placed between the two given vertices. And the GLUEE routine creates
a handle or kills a body node by placing a new edge between two given
vertices and by removing the second of two given faces. Completing
the set, the ESPLIT routine (explained in section 2.5) is included
as a convenient form of MKEV.
In principle, the advantages of the pure Euler primitives are
that they assure valid topology, full generality, reasonable
simplicity and they achieve a semantic level slightly higher than
that of manipulating the polyhedral nodes and links directly.
However, the Euler primitives only satisfy the first of the
conditions defining a solid polyhedron; imposing no particular
restrictions on surface orientation, face/vertex trivalence, face
planarity, face convexity or surface self intersection. In practice,
the Euler primitives serve as a topological foundation for coding
further routines which embody more algebra and geometry.
{|;λ10;JAFA}
BOX 3.1 {JC;T100,200,700;} THE EULER PRIMITIVES.
EULER MAKE PRIMITIVES:
1. BNEW ← MKBFV; Makes point polyhedron.
2. VNEW ← MKEV(F,V); Makes new edge and vertex.
VNEW ← ESPLIT(E); Makes new edge and vertex.
3. ENEW ← MKFE(V1,F,V2); Makes new face and edge.
4. ENEW ← GLUEE(F1,V1,F2,V2); Makes new edge, kills F2.
and makes a hole or kills a body.
EULER KILL PRIMITIVES:
1. QNEW ← KLBFEV(Q); Kills bodies, faces, edge and vertices.
2. FACE ← KLFE(E); Kills E and NFACE(E). Returns PFACE(E).
3. EDGE ← KLEV(V); Kills V and PED(V). Returns other E of V.
VERT ← KLEV(E); Kills E and NVT(E). Returns PVT(E).
4. FNEW ← UNGLUE(E); Kills E, makes F. Returns the new face,
and kills a hole or makes a body.
{|;λ30;T-1;JU;FAQ}
⊂3.2 Routines using Euler Primitives.⊃
Further methods of polyhedral construction can readily be
coded using the Euler primitives. For example, the routines listed in
box 3.2 illustrate the direct generation of simple prototypical
polyhedra, as well as contruction by sweeping, cutting, glueing,
copying and and duality.
{|;λ10;JAFA}
BOX 3.2 {JC} ROUTINES USING EULER PRIMITIVES.
1. BNEW ← MKCUBE(DX,DY,DZ); Create right rectangular prism.
2. BNEW ← MKCYLN(RADIUS,N,DZ); Create cylinder approximation.
3. BNEW ← MKBALL(RADIUS,M,N); Create sphere approximation.
4. FACE ← SWEEP(FACE,FLAG); Make prism on face (or sweep wire).
5. FACE ← ROTCOM(FACE); Rotation sweep wire face completion.
6. PEAK ← PYRAMID(FV); Make pyramid on a face (or vertex).
7. BODY ← GLUE(FACE1,FACE2); Removes face1 and face2.
8. BNEW ← MKCUT(BODY,X,Y,Z); Divide body at cutting plane.
9. QNEW ← MKCOPY(ENTITY); Copy an entity.
10. BODY ← FVDUAL(BODY); Apply face/vertex duality to a body.
{|;λ30;JU;FA}
The first three routines make cubic prisms as well as
polyhedral approximations to circular cylinders and spheres; or more
accurately, MKCUBE creates rectangular right parellelpipeds, MKCYLN
creates regular polygonal right cylinders and MKBALL creates hedrons
faceted by with two N-sided regular polar polygons and N*(M-1)
trapezoidal polygons with all vertices lying on the surface of a
sphere of a given radius.
Example of MKCUBE, MKCYLN and MKBALL with different arguments.
The inclusion of curved edges in GEOMED...
(the design of machine parts)
Lack of MKTETRA etc,
The three sweep primitives SWEEP, ROTCOM and PYRAMID
require the definition of three classes of non-solid Euler polyhedra:
wire, lamina and sheets.
A vertex can be sweep into a wire
a wire can be closed to form a lamina
a wire can be sweep into a sheet
and a sheet can be closed to form a sold polyhedron.
The sweep constructions were the original primitives of GEOMED (1970)
but lacked the generality and simplicity of the Euler primitives.
Comments on sheet metal based modeling.
⊂3.3 Euclidean Routines: Trams - Transforms and Frames.⊃
The Euclidean routines of GEOMED fall into four groups:
transformations, metrics, tram routines and space simulators. The
Euclidean transformation primitives are translation, rotation,
dilation and reflection (following Klein's Erlangen Program, 1872).
The Euclidean metric routines compute distances, angles, areas,
volumes and inertia tensors; while the tram routines create or alter
tram nodes which are explained below. The final group of routines
are for spatial simulations such as collision, propinquity, occupancy
and occultation.
Fundamental to all Euclidean routines is the curious fact
that a tram node has two interpretations: it may be used to specify a
coordinate system or it may be used to represent a Euclidean
transformation.
I have abandoned all use of the word <FRAME> because I do not wish
to risk confusion (or association) with the connotations of [Minsky],
[Winograd] and others. In geometric modeling, the word <frame> can be
replaced in all three of its graphics defintions: the <frame of
reference> or <coordinate frame> is now a <coordinate system> or a
<tram>, the <frame> of a movie film is now an <image>, the <frame>
of a display screen is now a <window> or <border>.
The Euclidean routines involving trams can be explained in
terms of the 4-D homogeneous coordinates found in computer graphics
then both frames of reference and transformations can be viewed as a
tensor. A <tensor> is a coordinate independent multi linear function.
{Q;|;λ10;JAFA}
BOX 3.2 {JC} TABLE OF EUCLIDEAN ROUTINES.
EUCLIDEAN TRANSFORMATIONS
TRAM ← TRANSL(XWD(TRAM,BODY),DX,DY,DZ);
TRAM ← ROTATE(XWD(TRAM,BODY),WX,WY,WZ);
TRAM ← SHRINK(XWD(TRAM,BODY),KX,KY,KZ);
TRAM ← APTRAM(ENTITY,TRAM);
TRAM ← INTRAM(TRAM);
TRAM ROUTINES
TRAM ← MKROT1(PAN,TILT,SWING); MAKE FROM EULER ANGLES.
TRAM ← MKFTRAM(FACE); MAKE FACE FRAME.
TRAM ← MKQFRM(WX,WY,WZ); MAKE FROM ROTATION VECTOR.
NORM(TRAM) ;NORMALIZATION TO UNIT VECTORS.
ORTHO1(TRAM) ;ORTHOGONALIZE BY WORST CASE.
ORTHO2(TRAM) ;ORTHOGONALIZE BY K ← (I CROSS J), J ← (K CROSS I).
{|;λ10;JU;FA}
⊂3.4 Euclidean Routines: Metrics and Space.⊃
METRIC ROUTINES.
DETERM(TRAM)
ANGL3V(V1,V2,V3)
DISTANCE(ENTITY,ENTITY);
SPATIAL SIMULATIONS.
⊂3.5 Image Synthesis: Perspective Projection.⊃
Perspective Projection.
The image synthesis includes perspective projection, hidden
line elimination, Z-clipping, display window transformation,
XY-clipping and the generation of a video file, or a vector display
file or some other disirable image data structure.
The perspective projection takes the 3-D world locus of every
potentially visible vertex and computes a 3-D camera center coordinate locus
followed by a perspective projection.
;PERSPECTIVE TRANSFORMATION.
XPP(V) ← SCALEX * XCC/ZCC; α where SCALEX = -FOCAL/PDX;
YPP(V) ← SCALEY * YCC/ZCC; α where SCALEY = -FOCAL/PDY;
ZPP(V) ← SCALEZ /ZCC; α where SCALEZ = -FOCAL/PDZ;
ZPP(V) IS POSITIVE WHEN VERTEX IS INVIEW. ←←← NOTA BENE.
⊂3.6 Image Synthesis: Clipping.⊃
Z Clipping.
2-D Clipping.
⊂3.7 Image Analysis: Interface to CRE.⊃